package com.hanxiaozhang.windowandmonotonestack;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给定一个整型数组arr，和一个整数num。某个arr中的子数组sub（连续的子数组），如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，返回arr中达标子数组的数量。
 *
 * @author hanxinghua
 * @create 2024/1/9
 * @since 1.0.0
 */
public class No2AllLessNumSubArray {


    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            int[] arr = getRandomArray(10);
            // arr = {7, 5, 3, 5, 8};
            System.out.println(Arrays.toString(arr));
            int i1 = method1(arr, 8);
            int i2 = method2(arr, 8);
            System.out.println("method1: " + i1);
            System.out.println("method2: " + i2);
            if (i1 != i2) {
                System.out.println("不相等");
            }

        }
    }


    public static int right(int[] arr, int sum) {
        if (arr == null || arr.length == 0 || sum < 0) {
            return 0;
        }
        int N = arr.length;
        int count = 0;
        for (int L = 0; L < N; L++) {
            for (int R = L; R < N; R++) {
                int max = arr[L];
                int min = arr[L];
                for (int i = L + 1; i <= R; i++) {
                    max = Math.max(max, arr[i]);
                    min = Math.min(min, arr[i]);
                }
                if (max - min <= sum) {
                    count++;
                }
            }
        }
        return count;
    }


    /**
     * 方法2
     * <p>
     * 找规律：
     * 规律1：如果子数组 arr[L...R]达标（即，符合 最大值 – 最小值 <= num），则其子数组
     * max(arr[L1.. R1]) - min(arr[L1.. R1])  <= num 必达标。
     * 规律2：如果arr[L...R]到达不达标状态，再扩大（R向右扩大）跟不达标。
     *
     * @param arr
     * @param num
     * @return
     */
    public static int method2(int[] arr, int num) {
        if (arr == null || arr.length == 0 || num < 0) {
            return 0;
        }
        // 单调递增双端队列
        LinkedList<Integer> qmin = new LinkedList<>();
        LinkedList<Integer> qmax = new LinkedList<>();
        // 窗口左指针，窗口右指针。窗口限定：[L..R)【左闭右开】 例如：[0,0）代表窗口中没有数
        int L = 0, R = 0;
        int res = 0;
        // L是开头位置，尝试每一个开头位置
        while (L < arr.length) {
            // 如果此时窗口的开头是L，下面的while工作：R向右扩到违规为止，
            // R是最后一个达标位置的再下一个，即R是不达标位置，R-1是最后一个达标位置。
            while (R < arr.length) {

                // 队列不为空 && 队列尾部元素 大于等于 当前元素 ，弹出尾部元素
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
                    qmin.pollLast();
                }
                qmin.addLast(R);

                // 队列不为空 && 队列尾部元素 晓宇等于 当前元素 ，弹出尾部元素
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                    qmax.pollLast();
                }
                qmax.addLast(R);

                // 必须满足：最大值 – 最小值 <= num  -> 最大值 – 最小值 > num
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break;
                }
                R++;
            }
            // 规律1 + 规律2
            res = res + R - L;
            // L位置将过期，移动一下
            if (qmin.peekFirst() == L) {
                qmin.pollFirst();
            }
            if (qmax.peekFirst() == L) {
                qmax.pollFirst();
            }
            L++;
        }
        return res;
    }


    /**
     * 方法1
     * 笨方法：三层循环
     * <p>
     * 第一层循环，控制左指针位置
     * 第二层循环，控制右指针位置
     * 第三层循环，比较窗口中的最大值和最小值
     *
     * @param arr
     * @param num
     * @return
     */
    public static int method1(int[] arr, int num) {
        if (arr == null || arr.length == 0 || num < 0) {
            return 0;
        }

        int result = 0;
        // 左指针位置
        for (int i = 0; i < arr.length; i++) {
            // 右指针位置
            for (int j = i; j < arr.length; j++) {
                int max = arr[i], min = arr[i];
                // 比较窗口中最大值 最小值
                for (int k = i; k <= j; k++) {
                    if (max < arr[k]) {
                        max = arr[k];
                    }
                    if (min > arr[k]) {
                        min = arr[k];
                    }
                }
                if (max - min <= num) {
                    result++;
                }
            }
        }

        return result;
    }

    /**
     * 随机生成数组
     *
     * @param len
     * @return
     */
    private static int[] getRandomArray(int len) {
        if (len < 0) {
            return null;
        }
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * 10);
        }
        return arr;
    }
}
